//KMP 算法实现
//扩展1:判断T1树，T2树，T2是否是T1的子树。
//https://www.yuque.com/huantaipingyang-jucwl/ipzeev/hf7gwn#NpbMf
//扩展2:添加相应字符，成为一个新的字符串，同时包含两个原来的字符串。
#include <string>
#include <iostream>
#include <map>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    static int getIndexof(std::string s,std::string m){
        if(s.empty()||m.empty()||s.length()<m.length()){
            return -1;
        }
        std::string str1=s;
        std::string str2=m;
        size_t i1=0;
        size_t i2=0;

        std::vector<int> next=getNextArray(m);
        while(i1<str1.length()&&i2<str2.length()){
            if(str1[i1]==str2[i2]){
                i1++;
                i2++;
            }else if(next[i2]==-1){
                i1++;
            } else {
                i2=next[i2];
            }
        }
        return i2==str2.length()?i1-i2:-1;
    }
    static std::vector<int> getNextArray(std::string str2){
        std::vector<int> next(str2.size(),-1);
        if(str2.size()==1) return next;
        next[0] = -1;
        next[1] = 0;
        size_t i=2;
        int cn=0;
        while(i<next.size()){
            if(str2[i-1]==str2[cn]){
                next[i++]=++cn;
            }else if(cn>0){
                cn=next[cn];
            }else{
                next[i++]=0;
            }
        }
        return next;
    }
};